home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d1 / diff25.arc / DIFF.DOC < prev    next >
Text File  |  1989-05-06  |  25KB  |  510 lines

  1.  
  2.  
  3.                            Diff - A Change Bar Tool
  4.  
  5.  
  6.                  by Peter van Es   CompuServe 72677,1417
  7.                       and mods by Steve Kraus 71531,2062
  8.           
  9.          As a person who has to maintain large amounts of
  10.          documentation and needs to be able to track changes through
  11.          successive revisions of the same document, I quickly felt the
  12.          need for a tool which would insert change bars into
  13.          documents.
  14.           
  15.          Remembering an article in Dr. Dobb's Journal, August 1987, by
  16.          Don Krantz, I found a utility written in C which would insert
  17.          Change Bars into existing document files in normal ASCII,
  18.          exactly what I needed.  I entered the program on my system,
  19.          converting it to Turbo C (mainly using the Turbo C library
  20.          routines for string comparisons) and tested it.  Whereas the
  21.          program worked fine on small text files, I had files for a
  22.          document of 900 K text to process.  The program's limitations
  23.          became painfully obvious very rapidly.  As it was written,
  24.          the program could not:
  25.           
  26.          -    deal with differences of over 200 lines, since the
  27.               resync module only looked 200 lines ahead;
  28.           
  29.          -    handle large text files since both uppercase and normal
  30.               versions of the line were stored in memory.
  31.           
  32.          Furthermore the program was very slow on dealing with small
  33.          changes (1 line inserted or deleted) due to the way the
  34.          resynchronization algorithm was implemented.
  35.           
  36.          Rather than re-designing the program I went through a series
  37.          of revisions on the program, tackling problems in small
  38.          chunks.  Perhaps it would have been better to re-design the
  39.          program, but the resulting program has solved all of these
  40.          limitations, and works just fine for my needs.  Some of the
  41.          existing limitations are documented at the end of this
  42.          document.
  43.           
  44.          Why have I documented the change process here?  Well, I
  45.          dislike two things:
  46.           
  47.          -    reinventing the wheel;
  48.           
  49.          -    optimizing programs by delving into optimizers, or
  50.               transforming parts into assembler routines.
  51.           
  52.          I believe in optimizing programs through the use of
  53.          different, more efficient algorithms.  Changing a high level
  54.          language into assembler in selected places may give you a 10%
  55.          speed increase, or, if you are lucky, a 50% increase.  By
  56.          altering the algorithm you can achieve improvements of 100%
  57.          to 1000% much more easily (depending on the problem, of
  58.          course).  I hope that my thought processes might be of use to
  59.          someone else, which is why I document them in this document.
  60.  
  61.  
  62.                                     Page 1
  63.  
  64.  
  65.  
  66.  
  67.  
  68.                            Diff - A Change Bar Tool
  69.  
  70.  
  71.  
  72.          The Improvements
  73.           
  74.           
  75.          The first problem was easy to solve.  The original program
  76.          stored a line read into memory both in normal format and in
  77.          uppercase format to allow case insensitive change bars to be
  78.          inserted.  Since Turbo C provides a subroutine to compare two
  79.          strings either with case sensitivity (strcmp()) or without
  80.          (stricmp()) the memory use of the program was halved at the
  81.          cost of some processing speed (deciding which one of the two
  82.          comparison routines to use).  Since these routines have been
  83.          optimized by Borland, they actually performed faster than the
  84.          routine that was originally in the program.
  85.           
  86.          The program included a good memory management scheme, which
  87.          ensured that every line of text was only read once, and
  88.          allocated memory would be freed at the earliest possible
  89.          opportunity, when a match has been found.  Since this scheme
  90.          is quite efficient, I decided to keep it as an essential part
  91.          of the program.
  92.           
  93.          Upon inspection the program was still CPU bound, spending
  94.          most of its time in string comparisons, with the disk drive
  95.          being idle.  In order to eliminate the time on most of these
  96.          comparisons, where the same line of text is compared over and
  97.          over again with other lines, a simple hash value of the
  98.          characters in the line is added to the structure containing
  99.          the line.  This hash value, or checksum, is an exclusive or
  100.          of all the characters in the line.  Instead of comparing
  101.          lines, the program now compares the pre-calculated checksums,
  102.          and only if they are equal, will it compare the line
  103.          character for character.  This reduced the amount of
  104.          processing on similar lines considerably.
  105.           
  106.          However, the program was still very slow, which was very
  107.          noticeable on files with lots of small changes.  Furthermore,
  108.          the program couldn't cope with changes of more than 200 lines
  109.          of text.  Checking the program revealed why this was so.  The
  110.          program would always take a line from file 1, and look up to
  111.          200 lines ahead in file 2, to find the matching line.  Then
  112.          it would take line 2 of file 1, and look 200 lines ahead from
  113.          the current line of file 2 again.  And so on, until it had
  114.          found a minimum of re-sync (which is a command line
  115.          modifiable value, normally set at 5) of un-changed lines.
  116.          This meant that in order to detect a 1 line change, the
  117.          program could perform up to a 1000 line comparisons.
  118.           
  119.          Since most changes two documents are small ones, I modified
  120.          the program so that it now starts by checking only 10 lines
  121.          ahead.  If that fails, it looks 20 lines ahead, then 40, 80
  122.          and so on until it runs out of memory.  There is no upper
  123.          limit on the number of lines, other than constrained by
  124.          memory.  As a result, a small change requires far fewer
  125.          comparisons and is detected far more rapidly.
  126.  
  127.  
  128.                                     Page 2
  129.  
  130.  
  131.  
  132.  
  133.  
  134.                            Diff - A Change Bar Tool
  135.  
  136.  
  137.  
  138.           
  139.          Big changes can also be detected, since the program does not
  140.          have the artificial constraint of 200 lines look ahead
  141.          anymore.  If it doesn't match on 80 lines it tries 160, then
  142.          320 and so on until it runs out of memory.  Since the memory
  143.          management function is quite efficient (discarding lines as
  144.          soon as a match has been found) quite a few lines can be
  145.          stored in memory.  That is also why the compact compilation
  146.          model is used, maximizing the amount of allocatable memory
  147.          for a small program.
  148.           
  149.          There still turned out a problem with this.  The program
  150.          could now almost always synchronize, but on extremely large
  151.          changes this was still very slow.  The reason for this is,
  152.          that every time the lookahead number of lines is doubled, the
  153.          program has to start at line 1 of file 1 again, but now
  154.          checking half the number of lines in file 2 for the second
  155.          time, and half for the first time.  Ie, the same line would
  156.          be compared against the same line lots of times anyway.  In
  157.          order to minimize the amount of repeat lookups which occur
  158.          every time that the lookahead lines are increased, the
  159.          program now assumes that after 40 lines couldn't match, the
  160.          change is probably very big, and the lookahead is set to 400
  161.          lines.  If it still doesn't match, it sets them at 800, 1600
  162.          etc until it runs out of memory.
  163.           
  164.          Regrettably, although this helped a little bit, it was only a
  165.          little bit, since for each of the 400 lines in file 1 each
  166.          and everyone of the 400 lines in file 2 are checked, leaving
  167.          the program still CPU bound.
  168.           
  169.          Then a brainwave hit.  If we can use the checksum (a value
  170.          between 0 and 255) to compare lines in the files, why can't
  171.          we use it to quickly locate a line already read in for file
  172.          2?  So an array was created, with an entry for each possible
  173.          checksum value.  This entry is the start of an ordered linked
  174.          list, pointing to lines with the same checksum.  Rather than
  175.          having to check all lookahead lines in order to resync, the
  176.          program uses the checksum value of the line in file 1 to
  177.          index into the array of linked lists.  It then traverses the
  178.          list of lines with the same checksum, comparing the lines
  179.          until one has been found which is equal.  If none are found,
  180.          the program takes the next line from file 1, and repeats the
  181.          process.  If no match can be found at all, the program
  182.          restarts the lookahead procedure with twice the number of
  183.          lines to look ahead.  In order to ensure that sufficient
  184.          lines are present, lookahead lines are read every time, which
  185.          means that the memory management still works and memory gets
  186.          cleared every time a synchronization has been detected.  At
  187.          one point a resync will either be found, or end of file
  188.          reached (or memory is full -- this will not happen soon since
  189.          matched lines are discarded from memory, so the change would
  190.          have to exceed the size of memory).
  191.           
  192.  
  193.  
  194.                                     Page 3
  195.  
  196.  
  197.  
  198.  
  199.  
  200.                            Diff - A Change Bar Tool
  201.  
  202.  
  203.  
  204.          However, since file 2 is not scanned sequentially but
  205.          randomly, the last line before a match (which is used to be
  206.          able to produce the "deleted from file 2" difference list) is
  207.          not available any more.  In order to allow for this, the line
  208.          structure now includes a pointer to the previous line, so
  209.          that the difference summary can still be printed.
  210.           
  211.          The nextline() and discard() functions maintain the line
  212.          structure list, and have been modified to maintain the
  213.          checksum array and the previous line list as well.  Resync
  214.          has been altered substantially in order to take advantage of
  215.          the array.  Minor modifications have been made to other
  216.          routines in order to provide extra error checking.
  217.           
  218.          As a result of these modifications the program now is much
  219.          faster especially with lots of small changes (due to the
  220.          lookahead line policy), and all large changes (due to the
  221.          checksum linked list).  So much so, in fact, that it is also
  222.          I/O bound (ie the disk drive is almost operating
  223.          continuously).  And it can handle bigger changes.  The
  224.          program now can put change bars into my 900 K of document
  225.          faster than my word processor can print it.
  226.           
  227.           
  228.          Limitations of the program.
  229.           
  230.          The main limitation of the program is due to the resynchro-
  231.          nization algorithm.  The program considers a file
  232.          resynchronized if it discovers a number of matched lines.
  233.          This number is set at 3 as a default, but can be modified
  234.          using the -r option.  However, the results of this algorithm
  235.          can be surprising.  When text has been duplicated (with more
  236.          than resync lines) and sandwiched in between new text, and
  237.          the old text has been left unchanged after the inserted text
  238.          (as in the following example), a match will be detected.  In
  239.          the example assume that resync is 3.
  240.           
  241.                       file 1                        file 2
  242.           
  243.                         A                             P
  244.                         B _______                     Q
  245.                         C        \                    R
  246.                         D ______  \__________________ B
  247.                         E ____  \                     C
  248.                         F     \  \___________________ D
  249.                         G      \                      S
  250.                         H _     \                     T
  251.                         I  \     \                    B
  252.                             \     \                   C
  253.                              \     \                  D
  254.                               \     \________________ E
  255.                  A false match...                     F
  256.                                 \                     G
  257.                                  \___________________ H
  258.  
  259.  
  260.                                     Page 4
  261.  
  262.  
  263.  
  264.  
  265.  
  266.                            Diff - A Change Bar Tool
  267.  
  268.  
  269.  
  270.          As can be seen above, BCD in file 1 will match with the first
  271.          occurrence of BCD in file 2.  And as a result, the second BCD
  272.          in file 2 will not match with the BCD in file 1.  (The
  273.          remainder, EFGH will match again).  A more logical match
  274.          would have been to leave the PQBCDRST sequence as a new
  275.          insert, and just match on the sequence BCDEFGH.  (Note that
  276.          the first match could have been avoided by selecting the
  277.          number of lines to be resynced to be larger than 3).
  278.           
  279.          A different algorithm, called the "longest common
  280.          subsequence" algorithm, will do just that automatically.  It
  281.          will select the longest matching sequence in the file and use
  282.          that as a basis for selecting the second longest matching
  283.          sequence both above and below the longest matching sequence
  284.          just found, and so on until all sequences have been found.
  285.          This method is also particularly suitable for implementation
  286.          using hashing.  However, a disadvantage of this algorithm is
  287.          that no lines can be discarded until both files have been
  288.          processed in their entirety.  As a result either lines have
  289.          to be kept on disk (for instance storing the lseek() value in
  290.          the line buffer with the checksum, so that lines can be
  291.          retrieved from disk using direct access), or the size of the
  292.          files that can be processed is limited.  Furthermore, since
  293.          the program will recursively check for matching subsequences
  294.          (compare it for instance with CAR Hoare's QuickSort
  295.          algorithm) this algorithm will produce better difference
  296.          reports only at the cost of much more computer time.  Thus
  297.          this algorithm is used most often on mini-computer systems.
  298.           
  299.          Note that a mix between the "longest common subsequence"
  300.          algorithm as described above, and the "scan until next match"
  301.          as implemented in the program presented here can be
  302.          implemented to good effect.  Rather than having a minimum
  303.          number of lines before resync is achieved, select a maximum
  304.          number of lines after which a matching subsequence is
  305.          considered the longest, causing the file to be split.  By
  306.          setting this number as one larger than the largest sequence
  307.          which occurs more than once in a file (eg 100 lines) the
  308.          program will produce the same results as the unconstrained
  309.          version of the program, in less processing time.
  310.           
  311.          A final limitation of the program is due to the fact that it
  312.          compares files on a line by line basis.  This is fine for for
  313.          instance program source code, but gives problems with most
  314.          automatic paragraph reformatting features available in word
  315.          processors.  The result of inserting a word in one sentence
  316.          can often be a re-format of several lines of text in the
  317.          paragraph.  Although in reality those sentences have not
  318.          changed, the program will think they are changed.
  319.           
  320.          The solution is to perform the comparison on a sentence by
  321.          sentence (or word by word) basis rather than line by line.
  322.          The difficulty is however not in the synchronization
  323.          algorithm (since that can stay as it is), but in the
  324.  
  325.  
  326.                                     Page 5
  327.  
  328.  
  329.  
  330.  
  331.  
  332.                            Diff - A Change Bar Tool
  333.  
  334.  
  335.  
  336.          algorithm which inserts change bars on the correct line in
  337.          the correct place in the document.  You would have to store a
  338.          representation of the original line of text somewhere, and
  339.          use a pointer to associate every word with the line from
  340.          which it came.  This modification is left as an exercise for
  341.          the reader, however.  If I ever get to it, I'll put the
  342.          resulting code in Public Domain again.
  343.           
  344.           
  345.          Using the diff program.
  346.           
  347.          diff - text file differencer and change barrer
  348.          usage: diff [option{option}] newfile oldfile [barfile]
  349.           
  350.          Where the options are optional and can be inserted in any order
  351.          except for the -n and -o option (which must appear in that
  352.          order).  Newfile and Oldfile are required (you don't want to
  353.          compare a file against nothing, do you?).  Barfile is optional,
  354.          used if you want a file with change bars in it as output.
  355.           
  356.          The options are:
  357.           
  358.            -t   trace operation, default off
  359.            -b n change Bar column in barfile, default 78
  360.            -h n Header lines to skip at top of page, default 0
  361.            -f n Footer lines to skip at bottom of page, default = 0
  362.            -p n Page size (embedded form feeds override) default = 66
  363.            -c   Case. uppercase/lowercase is significant (default is off)
  364.            -r n Resync lines that must match before files are considered 
  365.                 synced after differences are found. default = 3
  366.            -m n left Margin to start comparison, default = 0
  367.            -n   Number display line number instead of page & line
  368.                 number on output (default is pages/line numbers)
  369.            -w   White blank lines are considered significant (default is not)
  370.            -s   Screen listing off (default is on)
  371.            -u n Updated NEWFILE pages to skip before compare. default = 0,
  372.                 also sets -o.
  373.            -o n OLDFILE pages in skip before compare.  Must come after -u.
  374.                 default = 0
  375.           
  376.          The Trace option (-t) only shows if the program has been
  377.          compiled with the debug option on.  It shows debug messages.
  378.           
  379.          The Bar-column option (-b) selects the column in which the
  380.          vertical bar will be placed.  The default is column 78.
  381.          Column 0 will put it in the left most position on the page.
  382.          If your program contains embedded tabs, these are not
  383.          expanded automatically to ensure that when the bar should
  384.          appear in column 78, it actually does appear there.  So use
  385.          the option -b 0 in this case.
  386.           
  387.  
  388.                                     Page 6
  389.  
  390.  
  391.  
  392.  
  393.  
  394.                            Diff - A Change Bar Tool
  395.  
  396.  
  397.  
  398.          The Header option (-h) and Footer option (-f) allow you to
  399.          specify the number of lines to skip at the top of the page
  400.          and the bottom of the page for headers and footers.  You
  401.          don't usually want change bars just because the date or page
  402.          numbering of a file has changed.
  403.           
  404.          The Page length option (-p) allows you to specify the number
  405.          of lines per page.  66 is the Default.
  406.          The Case Sensitive (-c) option will insert change bars if
  407.          just the case of text has changed.  The default is no case
  408.          sensitivity, so that for instance changing "New york" into
  409.          "New York" does not generate a change bar.  For case
  410.          sensitive language's program listings you'll want to use the
  411.          -c option.
  412.           
  413.          The Resync option (-r) specifies the number of lines that
  414.          must match before the files are considered re-synced.  The
  415.          limitations of this parameter have been discussed above.  The
  416.          default is 3.  For program source code you'll want to
  417.          experiment with slightly larger values.
  418.           
  419.          The White option (-w) makes blank lines significant.  The
  420.          default is that they are not significant.  I never use this
  421.          option, but perhaps you have a need for it.
  422.           
  423.          The Screen option (-s) turns off the screen listing of the
  424.          differences.  This speeds up the program when you are not
  425.          interested in the differences list, or when you use the
  426.          program in a batch file.  Note that the program will give an
  427.          error message if you specify the -s option and no bar file
  428.          (since then all it would do is waste computer time).  The
  429.          differences list to screen has the following format:
  430.           
  431.          002:12<This text has been added to the newfile on page 2,
  432.          002:13<lines 12 and 13.
  433.          002:12>This line has been deleted from oldfile, page 2 and
  434.          002:13>lines 12 and 13 and 14.  Note that every time a match
  435.          002:14>has been found a blank line is printed first.
  436.           
  437.          (Note the direction of the arrows: < for insertion into the
  438.          newfile, >for deletion (extraction if you like) from the
  439.          oldfile to the newfile).
  440.           
  441.          The Newfile skip option (-n) and the Oldfile skip option (-o)
  442.          allow you to skip pages at the beginning of the file for
  443.          header pages and contents lists and the like, where you are
  444.          not interested in change bars.  Note that the -n option sets
  445.          the -o option (unless you override the -o setting by
  446.          explicitly including it in case contents lists are different
  447.          lengths).
  448.  
  449.  
  450.          Note that a space is required between a switch character and
  451.          its value.  Use "-r 5", not "-r5" or "/r5". - SK
  452.  
  453.  
  454.  
  455.                                     Page 7
  456.  
  457.  
  458.  
  459.  
  460.  
  461.                            Diff - A Change Bar Tool
  462.  
  463.  
  464.          Notes on Modifications by Steve Kraus.  First, let me say
  465.          thanks for the invaluable tool by Don Krantz and extensively
  466.          modified by Peter van Es.  I have used this program often.
  467.          But I am a programmer/analyst by profession.  And DIFF is
  468.          designed to compare documentation on a page/line basis
  469.          instead of a program source code basis.
  470.  
  471.          I often redirect the output from DIFF to another file or Vern
  472.          Buerg's LIST utility for perusal.  DIFF originally wrote all
  473.          of its output and error messages to STDOUT.  I added usage of
  474.          STDERR for the program version and error message lines, with
  475.          'screen' output and the help message written to STDOUT.
  476.  
  477.          When I first started using DIFF, I had trouble using the
  478.          switch options until I browsed through the source code.  I am
  479.          accustomed to using the forward slash switch character.  So I
  480.          added recognition for the additional "/" switch character and
  481.          recognition of the upper and lower case switches.  I modified
  482.          the help message to supply the keywords matching the options,
  483.          such as 'Screen' for -s.
  484.  
  485.          I'm more interested in the line number instead of the page
  486.          number.  Several PC editors enable you to start right at a
  487.          given line number.  I wanted the difference display to show
  488.          line numbers instead of the page : line combination.  So I
  489.          added the line numbering switch, called "-n" in honor of DOS
  490.          utilities FIND, GREP, and FC.  I renamed the old -n switch to
  491.          -u for Update file (sorry, Peter)
  492.  
  493.          I've been writing test set diagnostic software for HP9000
  494.          Basic systems.  The HP Basic editor is miserable.  After
  495.          transferring the saved Ascii files over to PC for editting
  496.          and printing, I would run DIFF on program files to verify the
  497.          program version changes.  Unfortunately, HP Basic renumbers
  498.          source lines automatically for inserted lines, changing the
  499.          content of every line.  So I devised the -m n Margin switch,
  500.          so I could ignore the mandatory Basic line numbers at the
  501.          beginning of every line.  The checksum and line comparison
  502.          begins at the "/M 5" left margin column, if specified.
  503.  
  504.          Plans for the next DIFF?  Another logical change (for the
  505.          future) would be to add a right margin column too.  I'd like
  506.          to modify option switch processing to allow the option value
  507.          to be catenated against the switch name.  That is, allow
  508.          switches of the format:  -b5  or  /R7  instead of requiring
  509.          the space between the value and the switch name:  -b 5 -r 7
  510.